package datastructure;

/*
 *  @类名: SqStack
 *  @作者:马萍 王雅萱
 *  @班级：23级网络空间安全
 *  @时间:11.3
 *  @描述: 栈的顺序表实现,栈的顺序表实现，通过数组来存储栈元素，实现了栈的基本操作，如改变栈容量、入栈、出栈、判断栈空、取栈顶元素等
 */
public class SqStack<E> implements Stack<E> {
    final int initcapacity = 10; // 顺序栈的初始容量(常量)，这里将其初始化为10，它决定了栈创建时的初始大小
    private int capacity; // 存放顺序栈的容量
    private E[] data; // 存放顺序栈中元素
    private int top; // 存放栈顶指针

    // 构造方法，实现data和size初始化      马萍
    public SqStack() {            //将顺序栈的容量初始化为预先定义的初始容量值，即把capacity设置为initcapacity的值，这里就是10。
        capacity = initcapacity;  //通过强制类型转换创建一个指定容量（即capacity的值）的泛型数组，用于存储栈元素。
        data = (E[]) new Object[capacity];      //初始化栈顶指针为 -1，表明栈当前为空，没有元素，栈顶位置在数组的起始位置之前
        top = -1;
    }

    // 改变栈容量  马萍
    private void updatecapacity(int newcapacity) { // 创建一个新的指定容量（即newcapacity的值）的泛型数组，用于替换原有的存储数组
        E[] newData = (E[]) new Object[newcapacity]; // 将原数组中的元素依次复制到新数组中，确保数据的完整性。通过循环遍历原数组中已存储元素的索引范围（从0到top），将每个元素赋值到新数组的对应位置。
        for (int i = 0; i <= top; i++) {
            newData[i] = data[i];          // 将原数组引用指向新创建的数组，完成数组的替换操作，这样后续对数据的操作就会在新数组上进行

        }
        data = newData;
        // 更新栈的容量为新的容量值，即把capacity设置为newcapacity的值，使栈的容量与新数组的容量匹配。
        capacity = newcapacity;
    }
    // 判断栈是否为空 马萍
    // 判断栈是否为空的方法，实现了Stack接口中定义的empty方法。
    public boolean empty() {             // 通过比较栈顶指针是否为 -1来判断栈的状态，如果栈顶指针为 -1，则表示栈为空，返回true；否则返回false。
        return top == -1;
    }

    // 进栈
    // 进栈操作的方法，实现了Stack接口中定义的push方法。
    // 当需要将一个元素压入栈时，调用此方法并传入要入栈的元素作为参数。此方法会根据栈的当前容量情况进行必要的扩容操作，然后将元素放入栈顶位置。
    public void push(E e) {
        if (top + 1 == capacity) {            // 如果栈顶指针加1后等于当前栈的容量，说明栈已满，需要进行扩容操作以容纳新元素。
            updatecapacity(capacity * 2);    // 调用updatecapacity方法将栈的容量扩大为原来的两倍，以满足新元素入栈的需求。
        }
        top++;                             // 将栈顶指针向上移动一位（加1），使其指向新的栈顶位置，准备放入新元素。
        data[top] = e;
    }

    // 出栈  王雅萱
    // 出栈操作的方法，实现了Stack接口中定义的pop方法。
    // 当需要从栈中弹出一个元素时，调用此方法，它会返回弹出的元素，并根据栈的当前状态进行必要的缩容操作（如果满足缩容条件），然后将栈顶指针向下移动一位（减1）
    public E pop() {            // 如果栈为空，抛出运行时异常，表示无法进行出栈操作，因为栈中没有元素可供弹出。
        E element = data[top];               // 获取当前栈顶位置的元素，即要弹出的元素，将其暂存到变量element中。
        top--;                                 // 将栈顶指针向下移动一位（减1），使其指向新的栈顶位置，即原来栈顶元素下面的那个元素（如果存在的话）。
        if (top < capacity / 4 && capacity > initcapacity) {
            updatecapacity(capacity / 2);           // 如果栈顶指针小于当前栈容量的四分之一，并且当前栈容量大于初始容量，说明栈空间利用率过低，需要进行缩容操作。
        }                                                        // 调用updatecapacity方法将栈的容量缩小为原来的一半，以节省内存空间。
        return element;
    }

    // 取栈顶元素   王雅萱
    // 取栈顶元素的方法，实现了Stack接口中定义的peek方法。
    // 当需要获取栈顶元素但不弹出它时，调用此方法，它会返回栈顶元素，但栈顶指针位置不变，即栈的状态不会因为获取栈顶元素而改变。
    public E peek() {
        return data[top];                   // 返回当前栈顶位置的元素，即栈顶元素，完成获取栈顶元素的操作。
    }
}